package base.C00_Recursion;

/**
 * Calculate the max num of Array
 * 分治：不断拆分求最值
 * 伪代码：
 * arr。length/2
 * <p>
 * max(arr[0,n]) = max(arr[0,n/2],arr[n/2+1,n])
 */
public class C01_MaxNum {
    public static int calcMax(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return 0;
        }
        return getMax(arr, 0, arr.length - 1);
    }

    private static int getMax(int[] arr, int start, int end) {

        int length = end - start;
        // 递归终止条件
        if (length == 0)
            return arr[start];
        // recursion
        int mid = (start + length) >> 1;
        int leftMax = getMax(arr, start, mid);
        int rightMax = getMax(arr, mid + 1, end);
        return Math.max(leftMax, rightMax);
    }
}
